//给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。 
//
// 返回这三个数的和。 
//
// 假定每组输入只存在恰好一个解。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,2,1,-4], target = 1
//输出：2
//解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,0,0], target = 1
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 3 <= nums.length <= 1000 
// -1000 <= nums[i] <= 1000 
// -10⁴ <= target <= 10⁴ 
// 
// Related Topics 数组 双指针 排序 👍 1164 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

public class _16_ThreeSumClosest {
    public static void main(String[] args) {
        Solution solution = new _16_ThreeSumClosest().new Solution();
        int[] nums = {-1, 2, 1, -4};
        int target = 1;
        System.out.println(solution.threeSumClosest(nums, target));
    }

    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int delta = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];
                int other = twoSumLessThanK(nums, i + 1, target - num);
                int sum = num + other;
                if (Math.abs(delta) >= Math.abs(sum - target)) {
                    delta = sum - target;
                }
            }
            return delta + target;
        }

        private int twoSumLessThanK(int[] nums, int start, int k) {
            int left = start;
            int right = nums.length - 1;
            int delta = Integer.MAX_VALUE;
            while (left < right) {
                int l = nums[left];
                int r = nums[right];
                int sum = l + r;
                if (Math.abs(delta) >= Math.abs(k - sum)) {
                    delta = sum - k;
                }
                if (sum > k) {
                    right--;
                } else {
                    left++;
                }
            }
            return delta + k;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution1 {
        public int threeSumClosest(int[] nums, int target) {
            int min = Integer.MAX_VALUE;
            int res = 0;
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    for (int k = j + 1; k < nums.length; k++) {
                        int sum = nums[i] + nums[j] + nums[k];
                        if (Math.abs(sum - target) < min) {
                            res = sum;
                        }
                        min = Math.abs(sum - target) < min ? Math.abs(sum - target) : min;
                    }
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}